<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width,initial-scale=1"><title>算法 - 算法分析 | Zhang Shuo'blog</title><meta name="keywords" content="算法基础"><meta name="author" content="Zhang Shuo"><meta name="copyright" content="Zhang Shuo"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="算法 - 算法分析  算法 - 算法分析 数学模型 1. 近似 2. 增长数量级 3. 内循环 4. 成本模型   注意事项 1. 大常数 2. 缓存 3. 对最坏情况下的性能的保证 4. 随机化算法 5. 均摊分析   ThreeSum 1. ThreeSumSlow 2. ThreeSumBinarySearch 3. ThreeSumTwoPointer   倍率实验    数学模型1. 近">
<meta property="og:type" content="article">
<meta property="og:title" content="算法 - 算法分析">
<meta property="og:url" content="https://zhang-shuo-fr.gitee.io/hexo3/2021/12/06/notes/%E7%AE%97%E6%B3%95%20-%20%E7%AE%97%E6%B3%95%E5%88%86%E6%9E%90/index.html">
<meta property="og:site_name" content="Zhang Shuo&#39;blog">
<meta property="og:description" content="算法 - 算法分析  算法 - 算法分析 数学模型 1. 近似 2. 增长数量级 3. 内循环 4. 成本模型   注意事项 1. 大常数 2. 缓存 3. 对最坏情况下的性能的保证 4. 随机化算法 5. 均摊分析   ThreeSum 1. ThreeSumSlow 2. ThreeSumBinarySearch 3. ThreeSumTwoPointer   倍率实验    数学模型1. 近">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://zhang-shuo-fr.gitee.io/hexo3/img/15.jpg">
<meta property="article:published_time" content="2021-12-06T09:36:00.000Z">
<meta property="article:modified_time" content="2021-12-10T12:59:46.904Z">
<meta property="article:author" content="Zhang Shuo">
<meta property="article:tag" content="算法基础">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://zhang-shuo-fr.gitee.io/hexo3/img/15.jpg"><link rel="shortcut icon" href="/hexo3/img/mao_tou_xiang.jpg"><link rel="canonical" href="https://zhang-shuo-fr.gitee.io/hexo3/2021/12/06/notes/%E7%AE%97%E6%B3%95%20-%20%E7%AE%97%E6%B3%95%E5%88%86%E6%9E%90/"><link rel="preconnect" href="//cdn.jsdelivr.net"/><link rel="preconnect" href="//fonts.googleapis.com" crossorigin=""/><link rel="preconnect" href="//busuanzi.ibruce.info"/><link rel="manifest" href="/hexo3/pwa/manifest.json"/><link rel="apple-touch-icon" sizes="180x180" href="/hexo3/pwa/apple-touch-icon.png"/><link rel="icon" type="image/png" sizes="32x32" href="/hexo3/pwa/32.png"/><link rel="icon" type="image/png" sizes="16x16" href="/hexo3/pwa/16.png"/><link rel="mask-icon" href="/hexo3/pwa/safari-pinned-tab.svg" color="#5bbad5"/><link rel="stylesheet" href="/hexo3/css/index.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free/css/all.min.css" media="print" onload="this.media='all'"><link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Titillium+Web&amp;display=swap" media="print" onload="this.media='all'"><script>const GLOBAL_CONFIG = { 
  root: '/hexo3/',
  algolia: undefined,
  localSearch: {"path":"search.xml","languages":{"hits_empty":"找不到您查询的内容：${query}"}},
  translate: {"defaultEncoding":2,"translateDelay":0,"msgToTraditionalChinese":"繁","msgToSimplifiedChinese":"簡"},
  noticeOutdate: undefined,
  highlight: {"plugin":"highlighjs","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":false},
  copy: {
    success: '复制成功',
    error: '复制错误',
    noSupport: '浏览器不支持'
  },
  relativeDate: {
    homepage: true,
    post: true
  },
  runtime: '天',
  date_suffix: {
    just: '刚刚',
    min: '分钟前',
    hour: '小时前',
    day: '天前',
    month: '个月前'
  },
  copyright: undefined,
  lightbox: 'fancybox',
  Snackbar: undefined,
  source: {
    jQuery: 'https://cdn.jsdelivr.net/npm/jquery@latest/dist/jquery.min.js',
    justifiedGallery: {
      js: 'https://cdn.jsdelivr.net/npm/justifiedGallery/dist/js/jquery.justifiedGallery.min.js',
      css: 'https://cdn.jsdelivr.net/npm/justifiedGallery/dist/css/justifiedGallery.min.css'
    },
    fancybox: {
      js: 'https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@latest/dist/jquery.fancybox.min.js',
      css: 'https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@latest/dist/jquery.fancybox.min.css'
    }
  },
  isPhotoFigcaption: false,
  islazyload: true,
  isanchor: true
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = {
  title: '算法 - 算法分析',
  isPost: true,
  isHome: false,
  isHighlightShrink: undefined,
  isToc: true,
  postUpdate: '2021-12-10 20:59:46'
}</script><noscript><style type="text/css">
  #nav {
    opacity: 1
  }
  .justified-gallery img {
    opacity: 1
  }

  #recent-posts time,
  #post-meta time {
    display: inline !important
  }
</style></noscript><script>(win=>{
    win.saveToLocal = {
      set: function setWithExpiry(key, value, ttl) {
        if (ttl === 0) return
        const now = new Date()
        const expiryDay = ttl * 86400000
        const item = {
          value: value,
          expiry: now.getTime() + expiryDay,
        }
        localStorage.setItem(key, JSON.stringify(item))
      },

      get: function getWithExpiry(key) {
        const itemStr = localStorage.getItem(key)

        if (!itemStr) {
          return undefined
        }
        const item = JSON.parse(itemStr)
        const now = new Date()

        if (now.getTime() > item.expiry) {
          localStorage.removeItem(key)
          return undefined
        }
        return item.value
      }
    }
  
    win.getScript = url => new Promise((resolve, reject) => {
      const script = document.createElement('script')
      script.src = url
      script.async = true
      script.onerror = reject
      script.onload = script.onreadystatechange = function() {
        const loadState = this.readyState
        if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
        script.onload = script.onreadystatechange = null
        resolve()
      }
      document.head.appendChild(script)
    })
  
      win.activateDarkMode = function () {
        document.documentElement.setAttribute('data-theme', 'dark')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
        }
      }
      win.activateLightMode = function () {
        document.documentElement.setAttribute('data-theme', 'light')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
        }
      }
      const t = saveToLocal.get('theme')
    
          if (t === 'dark') activateDarkMode()
          else if (t === 'light') activateLightMode()
        
      const asideStatus = saveToLocal.get('aside-status')
      if (asideStatus !== undefined) {
        if (asideStatus === 'hide') {
          document.documentElement.classList.add('hide-aside')
        } else {
          document.documentElement.classList.remove('hide-aside')
        }
      }
    
    const fontSizeVal = saveToLocal.get('global-font-size')
    if (fontSizeVal !== undefined) {
      document.documentElement.style.setProperty('--global-font-size', fontSizeVal + 'px')
    }
    
    const detectApple = () => {
      if (GLOBAL_CONFIG_SITE.isHome && /iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)){
        document.documentElement.classList.add('apple')
      }
    }
    detectApple()
    document.addEventListener('pjax:complete', detectApple)})(window)</script><style type="text/css">#toggle-sidebar {left:100px}</style><meta name="generator" content="Hexo 5.4.0"></head><body><div id="loading-box"><div class="loading-left-bg"></div><div class="loading-right-bg"></div><div class="spinner-box"><div class="configure-border-1"><div class="configure-core"></div></div><div class="configure-border-2"><div class="configure-core"></div></div><div class="loading-word">加载中...</div></div></div><div id="web_bg"></div><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="avatar-img is-center"><img src= "" data-lazy-src="/hexo3/img/mao_tou_xiang.jpg" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="site-data"><div class="data-item is-center"><div class="data-item-link"><a href="/hexo3/archives/"><div class="headline">文章</div><div class="length-num">176</div></a></div></div><div class="data-item is-center"><div class="data-item-link"><a href="/hexo3/tags/"><div class="headline">标签</div><div class="length-num">45</div></a></div></div><div class="data-item is-center"><div class="data-item-link"><a href="/hexo3/categories/"><div class="headline">分类</div><div class="length-num">15</div></a></div></div></div><hr/><div class="menus_items"><div class="menus_item"><a class="site-page" href="/hexo3/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page" href="/hexo3/archives/"><i class="fa-fw fas fa-archive"></i><span> 时间轴</span></a></div><div class="menus_item"><a class="site-page" href="/hexo3/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div><div class="menus_item"><a class="site-page" href="/hexo3/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><i class="fa-fw fa fa-heartbeat"></i><span> 小窝</span><i class="fas fa-chevron-down expand"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/hexo3/music/"><i class="fa-fw fas fa-music"></i><span> 音乐</span></a></li><li><a class="site-page child" href="/hexo3/Gallery/"><i class="fa-fw fas fa-images"></i><span> 照片</span></a></li><li><a class="site-page child" href="/hexo3/movies/"><i class="fa-fw fas fa-video"></i><span> 电影</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="/hexo3/link/"><i class="fa-fw fas fa-link"></i><span> 友链</span></a></div><div class="menus_item"><a class="site-page" href="/hexo3/about/"><i class="fa-fw fas fa-heart"></i><span> 关于</span></a></div></div></div></div><div class="post" id="body-wrap"><header class="post-bg" id="page-header" style="background-image: url('/hexo3/img/15.jpg')"><nav id="nav"><span id="blog_name"><a id="site-name" href="/hexo3/">Zhang Shuo'blog</a></span><div id="menus"><div id="search-button"><a class="site-page social-icon search"><i class="fas fa-search fa-fw"></i><span> 搜索</span></a></div><div class="menus_items"><div class="menus_item"><a class="site-page" href="/hexo3/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page" href="/hexo3/archives/"><i class="fa-fw fas fa-archive"></i><span> 时间轴</span></a></div><div class="menus_item"><a class="site-page" href="/hexo3/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div><div class="menus_item"><a class="site-page" href="/hexo3/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><i class="fa-fw fa fa-heartbeat"></i><span> 小窝</span><i class="fas fa-chevron-down expand"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/hexo3/music/"><i class="fa-fw fas fa-music"></i><span> 音乐</span></a></li><li><a class="site-page child" href="/hexo3/Gallery/"><i class="fa-fw fas fa-images"></i><span> 照片</span></a></li><li><a class="site-page child" href="/hexo3/movies/"><i class="fa-fw fas fa-video"></i><span> 电影</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="/hexo3/link/"><i class="fa-fw fas fa-link"></i><span> 友链</span></a></div><div class="menus_item"><a class="site-page" href="/hexo3/about/"><i class="fa-fw fas fa-heart"></i><span> 关于</span></a></div></div><div id="toggle-menu"><a class="site-page"><i class="fas fa-bars fa-fw"></i></a></div></div></nav><div id="post-info"><h1 class="post-title">算法 - 算法分析</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="far fa-calendar-alt fa-fw post-meta-icon"></i><span class="post-meta-label">发表于</span><time class="post-meta-date-created" datetime="2021-12-06T09:36:00.000Z" title="发表于 2021-12-06 17:36:00">2021-12-06</time><span class="post-meta-separator">|</span><i class="fas fa-history fa-fw post-meta-icon"></i><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2021-12-10T12:59:46.904Z" title="更新于 2021-12-10 20:59:46">2021-12-10</time></span><span class="post-meta-categories"><span class="post-meta-separator">|</span><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/hexo3/categories/%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80/">算法基础</a></span></div><div class="meta-secondline"><span class="post-meta-separator">|</span><span class="post-meta-wordcount"><i class="far fa-file-word fa-fw post-meta-icon"></i><span class="post-meta-label">字数总计:</span><span class="word-count">1.3k</span><span class="post-meta-separator">|</span><i class="far fa-clock fa-fw post-meta-icon"></i><span class="post-meta-label">阅读时长:</span><span>5分钟</span></span><span class="post-meta-separator">|</span><span class="post-meta-pv-cv" id="" data-flag-title="算法 - 算法分析"><i class="far fa-eye fa-fw post-meta-icon"></i><span class="post-meta-label">阅读量:</span><span id="busuanzi_value_page_pv"></span></span></div></div></div></header><main class="layout" id="content-inner"><div id="post"><article class="post-content" id="article-container"><h1 id="算法-算法分析"><a href="#算法-算法分析" class="headerlink" title="算法 - 算法分析"></a>算法 - 算法分析</h1><!-- GFM-TOC -->
<ul>
<li><a href="#%E7%AE%97%E6%B3%95---%E7%AE%97%E6%B3%95%E5%88%86%E6%9E%90">算法 - 算法分析</a><ul>
<li><a href="#%E6%95%B0%E5%AD%A6%E6%A8%A1%E5%9E%8B">数学模型</a><ul>
<li><a href="#1-%E8%BF%91%E4%BC%BC">1. 近似</a></li>
<li><a href="#2-%E5%A2%9E%E9%95%BF%E6%95%B0%E9%87%8F%E7%BA%A7">2. 增长数量级</a></li>
<li><a href="#3-%E5%86%85%E5%BE%AA%E7%8E%AF">3. 内循环</a></li>
<li><a href="#4-%E6%88%90%E6%9C%AC%E6%A8%A1%E5%9E%8B">4. 成本模型</a></li>
</ul>
</li>
<li><a href="#%E6%B3%A8%E6%84%8F%E4%BA%8B%E9%A1%B9">注意事项</a><ul>
<li><a href="#1-%E5%A4%A7%E5%B8%B8%E6%95%B0">1. 大常数</a></li>
<li><a href="#2-%E7%BC%93%E5%AD%98">2. 缓存</a></li>
<li><a href="#3-%E5%AF%B9%E6%9C%80%E5%9D%8F%E6%83%85%E5%86%B5%E4%B8%8B%E7%9A%84%E6%80%A7%E8%83%BD%E7%9A%84%E4%BF%9D%E8%AF%81">3. 对最坏情况下的性能的保证</a></li>
<li><a href="#4-%E9%9A%8F%E6%9C%BA%E5%8C%96%E7%AE%97%E6%B3%95">4. 随机化算法</a></li>
<li><a href="#5-%E5%9D%87%E6%91%8A%E5%88%86%E6%9E%90">5. 均摊分析</a></li>
</ul>
</li>
<li><a href="#threesum">ThreeSum</a><ul>
<li><a href="#1-threesumslow">1. ThreeSumSlow</a></li>
<li><a href="#2-threesumbinarysearch">2. ThreeSumBinarySearch</a></li>
<li><a href="#3-threesumtwopointer">3. ThreeSumTwoPointer</a></li>
</ul>
</li>
<li><a href="#%E5%80%8D%E7%8E%87%E5%AE%9E%E9%AA%8C">倍率实验</a><!-- GFM-TOC --></li>
</ul>
</li>
</ul>
<h2 id="数学模型"><a href="#数学模型" class="headerlink" title="数学模型"></a>数学模型</h2><h3 id="1-近似"><a href="#1-近似" class="headerlink" title="1. 近似"></a>1. 近似</h3><p>N<sup>3</sup>/6-N<sup>2</sup>/2+N/3 ~ N<sup>3</sup>/6。使用 ~f(N) 来表示所有随着 N 的增大除以 f(N) 的结果趋近于 1 的函数。</p>
<h3 id="2-增长数量级"><a href="#2-增长数量级" class="headerlink" title="2. 增长数量级"></a>2. 增长数量级</h3><p>N<sup>3</sup>/6-N<sup>2</sup>/2+N/3 的增长数量级为 O(N<sup>3</sup>)。增长数量级将算法与它的具体实现隔离开来，一个算法的增长数量级为 O(N<sup>3</sup>) 与它是否用 Java 实现，是否运行于特定计算机上无关。</p>
<h3 id="3-内循环"><a href="#3-内循环" class="headerlink" title="3. 内循环"></a>3. 内循环</h3><p>执行最频繁的指令决定了程序执行的总时间，把这些指令称为程序的内循环。</p>
<h3 id="4-成本模型"><a href="#4-成本模型" class="headerlink" title="4. 成本模型"></a>4. 成本模型</h3><p>使用成本模型来评估算法，例如数组的访问次数就是一种成本模型。</p>
<h2 id="注意事项"><a href="#注意事项" class="headerlink" title="注意事项"></a>注意事项</h2><h3 id="1-大常数"><a href="#1-大常数" class="headerlink" title="1. 大常数"></a>1. 大常数</h3><p>在求近似时，如果低级项的常数系数很大，那么近似的结果是错误的。</p>
<h3 id="2-缓存"><a href="#2-缓存" class="headerlink" title="2. 缓存"></a>2. 缓存</h3><p>计算机系统会使用缓存技术来组织内存，访问数组相邻的元素会比访问不相邻的元素快很多。</p>
<h3 id="3-对最坏情况下的性能的保证"><a href="#3-对最坏情况下的性能的保证" class="headerlink" title="3. 对最坏情况下的性能的保证"></a>3. 对最坏情况下的性能的保证</h3><p>在核反应堆、心脏起搏器或者刹车控制器中的软件，最坏情况下的性能是十分重要的。</p>
<h3 id="4-随机化算法"><a href="#4-随机化算法" class="headerlink" title="4. 随机化算法"></a>4. 随机化算法</h3><p>通过打乱输入，去除算法对输入的依赖。</p>
<h3 id="5-均摊分析"><a href="#5-均摊分析" class="headerlink" title="5. 均摊分析"></a>5. 均摊分析</h3><p>将所有操作的总成本除于操作总数来将成本均摊。例如对一个空栈进行 N 次连续的 push() 调用需要访问数组的次数为 N+4+8+16+…+2N=5N-4（N 是向数组写入元素的次数，其余都是调整数组大小时进行复制需要的访问数组次数），均摊后访问数组的平均次数为常数。</p>
<h2 id="ThreeSum"><a href="#ThreeSum" class="headerlink" title="ThreeSum"></a>ThreeSum</h2><p>ThreeSum 用于统计一个数组中和为 0 的三元组数量。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">interface</span> <span class="title">ThreeSum</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">count</span><span class="params">(<span class="keyword">int</span>[] nums)</span></span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="1-ThreeSumSlow"><a href="#1-ThreeSumSlow" class="headerlink" title="1. ThreeSumSlow"></a>1. ThreeSumSlow</h3><p>该算法的内循环为 <code>if (nums[i] + nums[j] + nums[k] == 0)</code> 语句，总共执行的次数为 N(N-1)(N-2) = N<sup>3</sup>/6-N<sup>2</sup>/2+N/3，因此它的近似执行次数为 ~N<sup>3</sup>/6，增长数量级为 O(N<sup>3</sup>)。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">ThreeSumSlow</span> <span class="keyword">implements</span> <span class="title">ThreeSum</span> </span>&#123;</span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">count</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> N = nums.length;</span><br><span class="line">        <span class="keyword">int</span> cnt = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; N; i++) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = i + <span class="number">1</span>; j &lt; N; j++) &#123;</span><br><span class="line">                <span class="keyword">for</span> (<span class="keyword">int</span> k = j + <span class="number">1</span>; k &lt; N; k++) &#123;</span><br><span class="line">                    <span class="keyword">if</span> (nums[i] + nums[j] + nums[k] == <span class="number">0</span>) &#123;</span><br><span class="line">                        cnt++;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> cnt;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="2-ThreeSumBinarySearch"><a href="#2-ThreeSumBinarySearch" class="headerlink" title="2. ThreeSumBinarySearch"></a>2. ThreeSumBinarySearch</h3><p>将数组进行排序，对两个元素求和，并用二分查找方法查找是否存在该和的相反数，如果存在，就说明存在和为 0 的三元组。</p>
<p>应该注意的是，只有数组不含有相同元素才能使用这种解法，否则二分查找的结果会出错。</p>
<p>该方法可以将 ThreeSum 算法增长数量级降低为 O(N<sup>2</sup>logN)。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">ThreeSumBinarySearch</span> <span class="keyword">implements</span> <span class="title">ThreeSum</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">count</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">        Arrays.sort(nums);</span><br><span class="line">        <span class="keyword">int</span> N = nums.length;</span><br><span class="line">        <span class="keyword">int</span> cnt = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; N; i++) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = i + <span class="number">1</span>; j &lt; N; j++) &#123;</span><br><span class="line">                <span class="keyword">int</span> target = -nums[i] - nums[j];</span><br><span class="line">                <span class="keyword">int</span> index = BinarySearch.search(nums, target);</span><br><span class="line">                <span class="comment">// 应该注意这里的下标必须大于 j，否则会重复统计。</span></span><br><span class="line">                <span class="keyword">if</span> (index &gt; j) &#123;</span><br><span class="line">                    cnt++;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> cnt;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">BinarySearch</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span> <span class="title">search</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> l = <span class="number">0</span>, h = nums.length - <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">while</span> (l &lt;= h) &#123;</span><br><span class="line">            <span class="keyword">int</span> m = l + (h - l) / <span class="number">2</span>;</span><br><span class="line">            <span class="keyword">if</span> (target == nums[m]) &#123;</span><br><span class="line">                <span class="keyword">return</span> m;</span><br><span class="line">            &#125; <span class="keyword">else</span> <span class="keyword">if</span> (target &gt; nums[m]) &#123;</span><br><span class="line">                l = m + <span class="number">1</span>;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                h = m - <span class="number">1</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="3-ThreeSumTwoPointer"><a href="#3-ThreeSumTwoPointer" class="headerlink" title="3. ThreeSumTwoPointer"></a>3. ThreeSumTwoPointer</h3><p>更有效的方法是先将数组排序，然后使用双指针进行查找，时间复杂度为 O(N<sup>2</sup>)。</p>
<p>同样不适用与数组存在重复元素的情况。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">ThreeSumTwoPointer</span> <span class="keyword">implements</span> <span class="title">ThreeSum</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">count</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> N = nums.length;</span><br><span class="line">        <span class="keyword">int</span> cnt = <span class="number">0</span>;</span><br><span class="line">        Arrays.sort(nums);</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; N - <span class="number">2</span>; i++) &#123;</span><br><span class="line">            <span class="keyword">int</span> l = i + <span class="number">1</span>, h = N - <span class="number">1</span>, target = -nums[i];</span><br><span class="line">            <span class="keyword">while</span> (l &lt; h) &#123;</span><br><span class="line">                <span class="keyword">int</span> sum = nums[l] + nums[h];</span><br><span class="line">                <span class="keyword">if</span> (sum == target) &#123;</span><br><span class="line">                    cnt++;</span><br><span class="line">                    l++;</span><br><span class="line">                    h--;</span><br><span class="line">                &#125; <span class="keyword">else</span> <span class="keyword">if</span> (sum &lt; target) &#123;</span><br><span class="line">                    l++;</span><br><span class="line">                &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                    h--;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> cnt;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="倍率实验"><a href="#倍率实验" class="headerlink" title="倍率实验"></a>倍率实验</h2><p>如果 T(N) ~ aN<sup>b</sup>logN，那么 T(2N)/T(N) ~ 2<sup>b</sup>。</p>
<p>例如对于暴力的 ThreeSum 算法，近似时间为 ~N<sup>3</sup>/6。进行如下实验：多次运行该算法，每次取的 N 值为前一次的两倍，统计每次执行的时间，并统计本次运行时间与前一次运行时间的比值，得到如下结果：</p>
<table>
<thead>
<tr>
<th align="center">N</th>
<th align="center">Time(ms)</th>
<th align="center">Ratio</th>
</tr>
</thead>
<tbody><tr>
<td align="center">500</td>
<td align="center">48</td>
<td align="center">/</td>
</tr>
<tr>
<td align="center">1000</td>
<td align="center">320</td>
<td align="center">6.7</td>
</tr>
<tr>
<td align="center">2000</td>
<td align="center">555</td>
<td align="center">1.7</td>
</tr>
<tr>
<td align="center">4000</td>
<td align="center">4105</td>
<td align="center">7.4</td>
</tr>
<tr>
<td align="center">8000</td>
<td align="center">33575</td>
<td align="center">8.2</td>
</tr>
<tr>
<td align="center">16000</td>
<td align="center">268909</td>
<td align="center">8.0</td>
</tr>
</tbody></table>
<p>可以看到，T(2N)/T(N) ~ 2<sup>3</sup>，因此可以确定 T(N) ~ aN<sup>3</sup>logN。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">RatioTest</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> N = <span class="number">500</span>;</span><br><span class="line">        <span class="keyword">int</span> loopTimes = <span class="number">7</span>;</span><br><span class="line">        <span class="keyword">double</span> preTime = -<span class="number">1</span>;</span><br><span class="line">        <span class="keyword">while</span> (loopTimes-- &gt; <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">int</span>[] nums = <span class="keyword">new</span> <span class="keyword">int</span>[N];</span><br><span class="line">            StopWatch.start();</span><br><span class="line">            ThreeSum threeSum = <span class="keyword">new</span> ThreeSumSlow();</span><br><span class="line">            <span class="keyword">int</span> cnt = threeSum.count(nums);</span><br><span class="line">            System.out.println(cnt);</span><br><span class="line">            <span class="keyword">double</span> elapsedTime = StopWatch.elapsedTime();</span><br><span class="line">            <span class="keyword">double</span> ratio = preTime == -<span class="number">1</span> ? <span class="number">0</span> : elapsedTime / preTime;</span><br><span class="line">            System.out.println(N + <span class="string">&quot;  &quot;</span> + elapsedTime + <span class="string">&quot;  &quot;</span> + ratio);</span><br><span class="line">            preTime = elapsedTime;</span><br><span class="line">            N *= <span class="number">2</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">StopWatch</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">long</span> start;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">start</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        start = System.currentTimeMillis();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">double</span> <span class="title">elapsedTime</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">long</span> now = System.currentTimeMillis();</span><br><span class="line">        <span class="keyword">return</span> (now - start) / <span class="number">1000.0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
</article><div class="post-copyright"><div class="post-copyright__author"><span class="post-copyright-meta">文章作者: </span><span class="post-copyright-info"><a href="mailto:undefined">Zhang Shuo</a></span></div><div class="post-copyright__type"><span class="post-copyright-meta">文章链接: </span><span class="post-copyright-info"><a href="https://zhang-shuo-fr.gitee.io/hexo3/2021/12/06/notes/%E7%AE%97%E6%B3%95%20-%20%E7%AE%97%E6%B3%95%E5%88%86%E6%9E%90/">https://zhang-shuo-fr.gitee.io/hexo3/2021/12/06/notes/%E7%AE%97%E6%B3%95%20-%20%E7%AE%97%E6%B3%95%E5%88%86%E6%9E%90/</a></span></div><div class="post-copyright__notice"><span class="post-copyright-meta">版权声明: </span><span class="post-copyright-info">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明来自 <a href="https://zhang-shuo-fr.gitee.io/hexo3" target="_blank">Zhang Shuo'blog</a>！</span></div></div><div class="tag_share"><div class="post-meta__tag-list"><a class="post-meta__tags" href="/hexo3/tags/%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80/">算法基础</a></div><div class="post_share"><div class="social-share" data-image="/hexo3/img/15.jpg" data-sites="facebook,twitter,wechat,weibo,qq"></div><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/social-share.js/dist/css/share.min.css" media="print" onload="this.media='all'"><script src="https://cdn.jsdelivr.net/npm/social-share.js/dist/js/social-share.min.js" defer></script></div></div><div class="post-reward"><div class="reward-button button--animated"><i class="fas fa-qrcode"></i> 打赏</div><div class="reward-main"><ul class="reward-all"><li class="reward-item"><a href="/hexo3/img/wechat.jpg" target="_blank"><img class="post-qr-code-img" src= "" data-lazy-src="/hexo3/img/wechat.jpg" alt="微信"/></a><div class="post-qr-code-desc">微信</div></li><li class="reward-item"><a href="/hexo3/img/alipay.jpg" target="_blank"><img class="post-qr-code-img" src= "" data-lazy-src="/hexo3/img/alipay.jpg" alt="支付宝"/></a><div class="post-qr-code-desc">支付宝</div></li></ul></div></div><nav class="pagination-post" id="pagination"><div class="prev-post pull-left"><a href="/hexo3/2021/12/06/notes/%E7%AE%97%E6%B3%95/"><img class="prev-cover" src= "" data-lazy-src="/hexo3/img/4.jpg" onerror="onerror=null;src='/hexo3/img/404.jpg'" alt="cover of previous post"><div class="pagination-info"><div class="label">上一篇</div><div class="prev_info">算法</div></div></a></div><div class="next-post pull-right"><a href="/hexo3/2021/12/06/notes/%E7%AE%97%E6%B3%95%20-%20%E7%9B%AE%E5%BD%95/"><img class="next-cover" src= "" data-lazy-src="/hexo3/img/13.jpg" onerror="onerror=null;src='/hexo3/img/404.jpg'" alt="cover of next post"><div class="pagination-info"><div class="label">下一篇</div><div class="next_info">算法 - 目录</div></div></a></div></nav><div class="relatedPosts"><div class="headline"><i class="fas fa-thumbs-up fa-fw"></i><span>相关推荐</span></div><div class="relatedPosts-list"><div><a href="/hexo3/2021/12/06/notes/%E7%AE%97%E6%B3%95%20-%20%E5%85%B6%E5%AE%83/" title="算法 - 其它"><img class="cover" src= "" data-lazy-src="/hexo3/img/16.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2021-12-06</div><div class="title">算法 - 其它</div></div></a></div><div><a href="/hexo3/2021/12/06/notes/%E7%AE%97%E6%B3%95%20-%20%E5%B9%B6%E6%9F%A5%E9%9B%86/" title="算法 - 并查集"><img class="cover" src= "" data-lazy-src="/hexo3/img/19.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2021-12-06</div><div class="title">算法 - 并查集</div></div></a></div><div><a href="/hexo3/2021/12/06/notes/%E7%AE%97%E6%B3%95%20-%20%E6%A0%88%E5%92%8C%E9%98%9F%E5%88%97/" title="算法 - 栈和队列"><img class="cover" src= "" data-lazy-src="/hexo3/img/11.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2021-12-06</div><div class="title">算法 - 栈和队列</div></div></a></div><div><a href="/hexo3/2021/12/06/notes/%E7%AE%97%E6%B3%95%20-%20%E7%9B%AE%E5%BD%95/" title="算法 - 目录"><img class="cover" src= "" data-lazy-src="/hexo3/img/13.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2021-12-06</div><div class="title">算法 - 目录</div></div></a></div><div><a href="/hexo3/2021/12/06/notes/%E7%AE%97%E6%B3%95/" title="算法"><img class="cover" src= "" data-lazy-src="/hexo3/img/4.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2021-12-06</div><div class="title">算法</div></div></a></div><div><a href="/hexo3/2021/12/06/notes/%E7%AE%97%E6%B3%95%20-%20%E6%8E%92%E5%BA%8F/" title="算法 - 排序"><img class="cover" src= "" data-lazy-src="/hexo3/img/9.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2021-12-06</div><div class="title">算法 - 排序</div></div></a></div></div></div></div><div class="aside-content" id="aside-content"><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="fas fa-stream"></i><span>目录</span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#%E7%AE%97%E6%B3%95-%E7%AE%97%E6%B3%95%E5%88%86%E6%9E%90"><span class="toc-number">1.</span> <span class="toc-text">算法 - 算法分析</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%95%B0%E5%AD%A6%E6%A8%A1%E5%9E%8B"><span class="toc-number">1.1.</span> <span class="toc-text">数学模型</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#1-%E8%BF%91%E4%BC%BC"><span class="toc-number">1.1.1.</span> <span class="toc-text">1. 近似</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-%E5%A2%9E%E9%95%BF%E6%95%B0%E9%87%8F%E7%BA%A7"><span class="toc-number">1.1.2.</span> <span class="toc-text">2. 增长数量级</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-%E5%86%85%E5%BE%AA%E7%8E%AF"><span class="toc-number">1.1.3.</span> <span class="toc-text">3. 内循环</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#4-%E6%88%90%E6%9C%AC%E6%A8%A1%E5%9E%8B"><span class="toc-number">1.1.4.</span> <span class="toc-text">4. 成本模型</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%B3%A8%E6%84%8F%E4%BA%8B%E9%A1%B9"><span class="toc-number">1.2.</span> <span class="toc-text">注意事项</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#1-%E5%A4%A7%E5%B8%B8%E6%95%B0"><span class="toc-number">1.2.1.</span> <span class="toc-text">1. 大常数</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-%E7%BC%93%E5%AD%98"><span class="toc-number">1.2.2.</span> <span class="toc-text">2. 缓存</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-%E5%AF%B9%E6%9C%80%E5%9D%8F%E6%83%85%E5%86%B5%E4%B8%8B%E7%9A%84%E6%80%A7%E8%83%BD%E7%9A%84%E4%BF%9D%E8%AF%81"><span class="toc-number">1.2.3.</span> <span class="toc-text">3. 对最坏情况下的性能的保证</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#4-%E9%9A%8F%E6%9C%BA%E5%8C%96%E7%AE%97%E6%B3%95"><span class="toc-number">1.2.4.</span> <span class="toc-text">4. 随机化算法</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#5-%E5%9D%87%E6%91%8A%E5%88%86%E6%9E%90"><span class="toc-number">1.2.5.</span> <span class="toc-text">5. 均摊分析</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#ThreeSum"><span class="toc-number">1.3.</span> <span class="toc-text">ThreeSum</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#1-ThreeSumSlow"><span class="toc-number">1.3.1.</span> <span class="toc-text">1. ThreeSumSlow</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-ThreeSumBinarySearch"><span class="toc-number">1.3.2.</span> <span class="toc-text">2. ThreeSumBinarySearch</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-ThreeSumTwoPointer"><span class="toc-number">1.3.3.</span> <span class="toc-text">3. ThreeSumTwoPointer</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%80%8D%E7%8E%87%E5%AE%9E%E9%AA%8C"><span class="toc-number">1.4.</span> <span class="toc-text">倍率实验</span></a></li></ol></li></ol></div></div></div></div></main><footer id="footer" style="background-image: url('/hexo3/img/15.jpg')"><div id="footer-wrap"><div class="copyright">&copy;2020 - 2022 By Zhang Shuo</div><div class="framework-info"><span>框架 </span><a target="_blank" rel="noopener" href="https://hexo.io">Hexo</a><span class="footer-separator">|</span><span>主题 </span><a target="_blank" rel="noopener" href="https://github.com/jerryc127/hexo-theme-butterfly">Butterfly</a></div><div class="footer_custom_text">Hi, welcome to my blog!</div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="fas fa-book-open"></i></button><button id="font-plus" type="button" title="放大字体"><i class="fas fa-plus"></i></button><button id="font-minus" type="button" title="缩小字体"><i class="fas fa-minus"></i></button><button id="translateLink" type="button" title="简繁转换">簡</button><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside_config" type="button" title="设置"><i class="fas fa-cog fa-spin"></i></button><button class="close" id="mobile-toc-button" type="button" title="目录"><i class="fas fa-list-ul"></i></button><button id="go-up" type="button" title="回到顶部"><i class="fas fa-arrow-up"></i></button></div></div><div id="local-search"><div class="search-dialog"><div class="search-dialog__title" id="local-search-title">本地搜索</div><div id="local-input-panel"><div id="local-search-input"><div class="local-search-box"><input class="local-search-box--input" placeholder="搜索文章" type="text"/></div></div></div><hr/><div id="local-search-results"></div><span class="search-close-button"><i class="fas fa-times"></i></span></div><div id="search-mask"></div></div><div><script src="/hexo3/js/utils.js"></script><script src="/hexo3/js/main.js"></script><script src="/hexo3/js/tw_cn.js"></script><script src="https://cdn.jsdelivr.net/npm/instant.page/instantpage.min.js" type="module"></script><script src="https://cdn.jsdelivr.net/npm/vanilla-lazyload/dist/lazyload.iife.min.js"></script><script src="/hexo3/js/search/local-search.js"></script><script>var preloader = {
  endLoading: () => {
    document.body.style.overflow = 'auto';
    document.getElementById('loading-box').classList.add("loaded")
  },
  initLoading: () => {
    document.body.style.overflow = '';
    document.getElementById('loading-box').classList.remove("loaded")

  }
}
window.addEventListener('load',preloader.endLoading())</script><div class="js-pjax"></div><div class="aplayer no-destroy" data-id="000PeZCQ1i4XVs" data-server="tencent" data-type="artist" data-fixed="true" data-mini="true" data-listFolded="false" data-order="random" data-preload="none" data-autoplay="true" muted></div><script defer="defer" id="fluttering_ribbon" mobile="true" src="https://cdn.jsdelivr.net/npm/butterfly-extsrc@1/dist/canvas-fluttering-ribbon.min.js"></script><script id="canvas_nest" defer="defer" color="0,0,255" opacity="0.7" zIndex="-1" count="99" mobile="true" src="https://cdn.jsdelivr.net/npm/butterfly-extsrc@1/dist/canvas-nest.min.js"></script><script src="https://cdn.jsdelivr.net/npm/butterfly-extsrc@1/dist/activate-power-mode.min.js"></script><script>POWERMODE.colorful = true;
POWERMODE.shake = false;
POWERMODE.mobile = true;
document.body.addEventListener('input', POWERMODE);
</script><script id="click-heart" src="https://cdn.jsdelivr.net/npm/butterfly-extsrc@1/dist/click-heart.min.js" async="async" mobile="true"></script><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/aplayer/dist/APlayer.min.css" media="print" onload="this.media='all'"><script src="https://cdn.jsdelivr.net/npm/aplayer/dist/APlayer.min.js"></script><script src="https://cdn.jsdelivr.net/gh/metowolf/MetingJS@1.2/dist/Meting.min.js"></script><script src="https://cdn.jsdelivr.net/npm/pjax/pjax.min.js"></script><script>let pjaxSelectors = [
  'title',
  '#config-diff',
  '#body-wrap',
  '#rightside-config-hide',
  '#rightside-config-show',
  '.js-pjax'
]

if (false) {
  pjaxSelectors.unshift('meta[property="og:image"]', 'meta[property="og:title"]', 'meta[property="og:url"]')
}

var pjax = new Pjax({
  elements: 'a:not([target="_blank"])',
  selectors: pjaxSelectors,
  cacheBust: false,
  analytics: false,
  scrollRestoration: false
})

document.addEventListener('pjax:send', function () {

  // removeEventListener scroll 
  window.removeEventListener('scroll', window.tocScrollFn)
  window.removeEventListener('scroll', scrollCollect)

  typeof preloader === 'object' && preloader.initLoading()
  
  if (window.aplayers) {
    for (let i = 0; i < window.aplayers.length; i++) {
      if (!window.aplayers[i].options.fixed) {
        window.aplayers[i].destroy()
      }
    }
  }

  typeof typed === 'object' && typed.destroy()

  //reset readmode
  const $bodyClassList = document.body.classList
  $bodyClassList.contains('read-mode') && $bodyClassList.remove('read-mode')

})

document.addEventListener('pjax:complete', function () {
  window.refreshFn()

  document.querySelectorAll('script[data-pjax]').forEach(item => {
    const newScript = document.createElement('script')
    const content = item.text || item.textContent || item.innerHTML || ""
    Array.from(item.attributes).forEach(attr => newScript.setAttribute(attr.name, attr.value))
    newScript.appendChild(document.createTextNode(content))
    item.parentNode.replaceChild(newScript, item)
  })

  GLOBAL_CONFIG.islazyload && window.lazyLoadInstance.update()

  typeof chatBtnFn === 'function' && chatBtnFn()
  typeof panguInit === 'function' && panguInit()

  // google analytics
  typeof gtag === 'function' && gtag('config', '', {'page_path': window.location.pathname});

  // baidu analytics
  typeof _hmt === 'object' && _hmt.push(['_trackPageview',window.location.pathname]);

  typeof loadMeting === 'function' && document.getElementsByClassName('aplayer').length && loadMeting()

  // Analytics
  if (false) {
    MtaH5.pgv()
  }

  // prismjs
  typeof Prism === 'object' && Prism.highlightAll()

  typeof preloader === 'object' && preloader.endLoading()
})

document.addEventListener('pjax:error', (e) => {
  if (e.request.status === 404) {
    pjax.loadUrl('/404.html')
  }
})</script><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script></div></body></html>